/*
题目：前序遍历构造二叉搜索树
给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。

保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/
 */
public class BstFromPreorder {
    public TreeNode bstFromPreorder(int[] preorder) {
        //单调栈
        Stack<TreeNode> stack = new Stack<> ();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);

        for (int i = 1; i < preorder.length;) {
            if (stack.isEmpty() || stack.peek().val > preorder[i]) {
                TreeNode cur = new TreeNode(preorder[i]);
                stack.peek().left = cur;
                stack.push(cur);
                i++;
            } else {
                TreeNode cur = null;
                while (!stack.isEmpty() && stack.peek().val < preorder[i]) {
                    cur = stack.pop();
                }
                cur.right = new TreeNode(preorder[i++]);
                stack.push(cur.right);
            }
        }

        return root;
    }
}